Fu costruito tra il 1244 e il 1246 come ampliamento degli edifici comunali del Palazzo del Podestà (assieme al Palazzo del Capitano del popolo) e per questo chiamato Palatium Novum, ma le sue vicende storiche l'hanno da sempre legato alla figura di Re Enzo di Sardegna.

 

Appena tre anni dopo la sua costruzione, il Palatium Novum divenne la dimora coatta di Re Enzo di Sardegna, figlio dell'imperatore Federico II di Svevia, fatto prigioniero nei pressi di Modena durante la battaglia di Fossalta, che vide la vittoria dei bolognesi sulle truppe imperiali di Enzo di Svevia. Dopo la cattura, Re Enzo fu tenuto per alcuni giorni nel castello di Anzola dell'Emilia (dove si può ancora visitare quella che fu la sua prigione) e in seguito fu trasferito a Bologna, dove rimase per ventitré anni, dall'agosto del 1249 fino alla sua morte (avvenuta il 14 marzo 1272), probabilmente in ambienti opportunamente adibiti al secondo piano.

 

Al pian terreno venivano custoditi il Carroccio e le macchine da guerra, mentre al primo piano vi erano gli uffici del pretore e la cappella. Nel 1386 Antonio di Vincenzo realizzò in muratura la Sala del Trecento, poi adibita ad archivio comunale. L'ultimo piano fu pesantemente ristrutturato nel 1771 ad opera di Giovanni Giacomo Dotti.

 

Nel 1905 Alfonso Rubbiani ripristinò l'aspetto gotico dell'edificio ricostruendo le originarie merlature, le arcate del pianterreno, la scala quattrocentesca e riaprendo le finestre a trifora, operando tuttavia numerose aggiunte di fantasia dettate dalla moda neo-medievalista dell'epoca. Sulla destra del palazzo si trova ancora l'accesso alla cappella di Santa Maria dei Carcerati, in cui si recavano i condannati a morte. A partide dal 1910, nell'ambito delle dello sventramento del Mercato di Mezzo per l'allargamento di via Rizzoli, vennero demoliti numerosi edifici che, nel corso dei secoli, gli erano cresciuti intorno, fra cui casa Campogrande e il voltone della corda, situato fra i due edifici.

 

Le facciate esterne del Palazzo Re Enzo si affacciano sulla Piazza del Nettuno, via Rizzoli e Piazza Re Enzo e sono state sottoposte a restauro conservativo nel 2003.

 

Numerose sono le leggende divulgate dai cronisti a proposito della cattura e della prigionia di re Enzo.

 

Si parla di una mancata fuga dal castello di Anzola dell'Emilia prima ancora che il re venisse portato a Bologna e successivamente di un riscatto che il padre avrebbe pagato ai bolognesi, col quale si sarebbe potuta erigere tutta la cerchia muraria della città ma che i bolognesi rifiutarono.

 

Pare che durante la prigionia Re Enzo passasse il giorno insieme ad altri prigionieri ma durante la notte venisse isolato in una gabbia appesa al soffitto e sorvegliato a vista.

 

Il Comune consentiva altresì ad Enzo di ricevere visite femminili: Enzo ricorda nel suo testamento tre figlie naturali. Una leggenda postuma gli attribuisce un quarto figlio nato dall'amore per una contadina, Lucia di Viadagola. Al bambino sarebbe stato dato il nome di Bentivoglio (per le parole che Enzo soleva dire alla sua amata, Amore mio, ben ti voglio), il quale sarebbe il capostipite leggendario della casata bolognese dei Bentivoglio.

 

Si racconta anche di una tentata fuga in una brenta, usata per trasportare il vino, fallita grazie ad una vecchia signora che vide i lunghi capelli biondi del re.

 

Dopo 23 anni di prigionia Enzo morì e fu sepolto nella Basilica di San Domenico come lui stesso aveva desiderato e dove ancora oggi è presente la sua tomba.